package com.github.yangyishe.p100;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 无重复字符的最长子串
 * https://leetcode.cn/problems/longest-substring-without-repeating-characters/
 * The type Problem 3.
 *
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 *
 *
 * 示例 1:
 *
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 *
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 *
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *
 *
 * 提示：
 *
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 */
public class Problem03 {
    public static void main(String[] args) {
        Problem03 problem03 = new Problem03();
        String s="pwwkew";
        int i = problem03.lengthOfLongestSubstring(s);
        System.out.println(i);
    }

    public int lengthOfLongestSubstring(String s) {
        Queue<Character> queue=new LinkedList<>();
        char[] chars = s.toCharArray();
        int maxLen=0;
        for (char c : chars) {
            if (queue.contains(c)) {
                while(true){
                    Character poll = queue.poll();
                    if (poll==null||poll==c) {
                        break;
                    }
                }
            }
            queue.offer(c);
            if (maxLen<queue.size()) {
                maxLen=queue.size();
            }
        }
        return maxLen;
    }
}
